package base_Suanfa.erchashu;

import bean.TreeNode;

import java.util.*;
import java.util.concurrent.LinkedBlockingDeque;
//二叉树遍历方法
public class erchashu_bianli {
    public static void preOrder(TreeNode root,int i,int a[]){
        if(root==null) return;
       // System.out.print(root.val+"="+i+"  ");
        a[0]=Math.max(a[0],i);
        preOrder(root.left,i+1,a);
        preOrder(root.right,i+1,a);

    }
    public static void preOrder2(TreeNode root){
//        if(root==null) return;
//        Stack<TreeNode> stack=new Stack<>();
//        stack.push(root);
//        while (!stack.isEmpty()){
//            TreeNode t=stack.pop();
//            System.out.print(t.val);
//            if(t.right!=null)
//                stack.push(t.right);
//            if(t.left!=null)
//                stack.push(t.left);
//        }

    }
    public static void minOrder(TreeNode root) {
        if (root == null) return;
        minOrder(root.left);
        System.out.print(root.val);
        minOrder(root.right);
    }
    public static void minOrder1(TreeNode root) {
        if (root == null) return ;
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        while(!stack.isEmpty()||cur!=null ){
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode t=stack.pop();
            System.out.print(t.val);
            if(t.right!=null)
                cur=t.right;

        }

    }
    public static void finalOrder(TreeNode root){
        if(root==null) return;
        finalOrder(root.left);
        finalOrder(root.right);
        System.out.print(root.val);
    }
    public static void finalOrder1(TreeNode root){
//        if(root==null) return;
//        Stack<TreeNode > stack=new Stack<>();
//        Stack<TreeNode> stack1=new Stack<>();   //用来倒序输出结果，前序遍历是根右左，stack是根左右，那么stack1后序遍历输出为右左后
//        stack.push(root);
//        while (!stack.isEmpty()){
//            TreeNode t=stack.pop();
//            stack1.push(t);
//            if(t.left!=null)
//                stack.push(t.left);
//            if(t.right!=null)
//                stack.push(t.right);
//        }
//        while (!stack1.isEmpty()){
//            System.out.print(stack1.pop());
//        }

    }
    //广度遍历
    public  static List<List<Integer>> chengci(TreeNode root) {
        List<List<Integer>> listList=new ArrayList<>();
        if (root == null) return null ;
        Queue<TreeNode > queue=new LinkedList<>();
        queue.offer(root);
        List<Integer> temp;
        while (!queue.isEmpty()){
            int size=queue.size();
            temp=new ArrayList<>();
            while (--size>=0) {
                TreeNode t = queue.poll();
                temp.add(t.val);
                if (t.left != null) {
                    queue.offer(t.left);   //先加左边
                }
                if (t.right != null) {
                    queue.offer(t.right);  //再加右边
                }
            }
            listList.add(temp);
        }
        return listList;
//        List<List<Integer>> listList=new ArrayList<>();
//       if (root == null) return null ;
//       Queue<TreeNode > queue=new LinkedList<>();
//       queue.offer(root);
//        while (!queue.isEmpty()){
//            int m=queue.size();
//            List<Integer> list=new ArrayList<>();
//            while (--m>=0){
//                TreeNode treeNode=queue.poll();
//                   list.add(treeNode.val);
//                if(treeNode.left!=null){
//                    queue.add(treeNode.left);
//                }
//                if(treeNode.right!=null){
//                    queue.add(treeNode.right);
//                }
//            }
//            listList.add(list);
//        }
//        return listList;
    }
   //二叉树的镜像
      public static  void  jingxiang(TreeNode node){
        if(node==null)
            return;
        TreeNode t=node.left;
        node.left=node.right;
        node.right=t;
   jingxiang(node.left);
   jingxiang(node.right);
      }
    public static void main(String[] args) {
        TreeNode t=new TreeNode(1);
        TreeNode t1=new TreeNode(2);
        TreeNode t2=new TreeNode(3);
        TreeNode t3=new TreeNode(4);
        TreeNode t4=new TreeNode(5);
        TreeNode t5=new TreeNode(6);
        TreeNode t6=new TreeNode(7);
        t.left=t1;
        t.right=t2;
        t1.left=t3;
        t1.right=t4;
        t2.right=t5;
        t4.left=t6;
//        int a[]={0};
//        preOrder(t,1,a);
//        System.out.println(a[0]);
//        System.out.println("递归先序输出");
//      preOrder(t,1);
//       System.out.println();
//       System.out.println("非递归先序输出");
//      preOrder2(t);
        System.out.println();
        System.out.println("递归中序输出");
        minOrder(t);
        jingxiang(t);
        System.out.println();
        System.out.println("非递归中序输出");
        minOrder1(t);
//        System.out.println();
//        System.out.println("递归后序输出");
//        finalOrder(t);
//        System.out.println();
//        System.out.println("非递归后序输出");
//    finalOrder1(t);
//        System.out.println();
//        System.out.println("层次遍历为");
//        System.out.println(chengci(t));
    }
}
